import com.alibaba.fastjson.JSON;

import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.RecursiveTask;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-12-27
 **/

public class Main {

    /**
     * 快排
     */

    private Random random = new Random();

    private void fastSort(int[] arr) {
        this.splitSortArr(arr, 0, arr.length - 1);
    }

    /**
     * 1. 寻找中间值
     * 2. 切割递归继续寻找
     */
    private void splitSortArr(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int baseIndex = this.random.nextInt(right - left + 1) + left;
        this.swap(arr, left, baseIndex);
        int index = this.getMidIndex(arr, left, right);
        this.splitSortArr(arr, left, index);
        this.splitSortArr(arr, index + 1, right);
    }

    private int getMidIndex(int[] arr, int left, int right) {

        int num = arr[left];

        while (left < right) {

            // 从右开始找到一个比num小的数字
            while (left < right && num <= arr[right]) {
                right--;
            }
            this.swap(arr, left, right);
            // 从左开始找到一个比num大的数字
            while (left < right && num >= arr[left]) {
                left++;
            }
            this.swap(arr, left, right);
        }

        return left;
    }

    private void swap(int[] arr, int index1, int index2) {
        int num = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = num;
    }

    /**
     * 归并
     */
    private void mergeSort(int[] arr) {
        this.dfs(arr, new int[arr.length], 0, arr.length - 1);
    }

    /**
     * 1. 切割递归
     * 2. 排序
     */
    private void dfs(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (right - left) / 2 + left;
        this.dfs(arr, temp, left, mid);
        this.dfs(arr, temp, mid + 1, right);
        this.sort(arr, temp, left, right);
    }

    /**
     * 排序, 想一想归并排序的图, 即两个有序数组形成一个有序数组
     */
    private void sort(int[] arr, int[] temp, int left, int right) {

        int mid = (right - left) / 2 + left;

        // 两个数组可以直接拼接, 已经有序
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }

        int startIndex1 = left;
        int startIndex2 = mid + 1;
        int index = left;

        while (startIndex1 <= mid && startIndex2 <= right) {
            int num1 = arr[startIndex1];
            int num2 = arr[startIndex2];
            if (num1 <= num2) {
                temp[index] = num1;
                startIndex1++;
            } else {
                temp[index] = num2;
                startIndex2++;
            }
            index++;
        }

        while (startIndex1 <= mid) {
            temp[index] = arr[startIndex1];
            startIndex1++;
            index++;
        }

        while (startIndex2 <= mid) {
            temp[index] = arr[startIndex2];
            startIndex2++;
            index++;
        }

        // 放回
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

    }


    public static void main(String[] args) throws ExecutionException, InterruptedException {
        Main main = new Main();
        int[] arr = {1, 4, 5, 6, 7, 1, 2, 5, 6, 7, 8, 2, 3, 4};
        main.fastSort(arr);
        main.mergeSort(arr);
        // [1,1,2,2,3,4,4,5,5,6,6,7,7,8]
        System.out.println(JSON.toJSONString(arr));
//        // 每个线程对应一个任务数组, 通过CAS窃取任务
//        ForkJoinPool forkJoinPool = new ForkJoinPool(1);
//        CalculateTask calculateTask = new CalculateTask(0, 20);
//        forkJoinPool.submit(calculateTask);
//        Integer integer = calculateTask.get();
//        System.out.println(integer);
    }

    private static class CalculateTask extends RecursiveTask<Integer> {

        private static final long serialVersionUID = 6915339777976374123L;
        private int start;
        private int end;
        private int threshold = 10;

        public CalculateTask(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        protected Integer compute() {

            System.out.println("初始" + Thread.currentThread().getName());
            if (this.end - this.start < this.threshold) {
                int num = 0;
                for (int i = this.start; i <= this.end; i++) {
                    num += i;
                }
                System.out.println(this.start + "~" + this.end);
                return num;
            } else {
                int mid = (this.end - this.start) / 2 + this.start;
                CalculateTask calculateTask1 = new CalculateTask(this.start, mid);
                CalculateTask calculateTask2 = new CalculateTask(mid + 1, this.end);
                // 将任务放入工作队列中
                System.out.println("放入" + Thread.currentThread().getName());
                calculateTask1.fork();
                calculateTask2.fork();
                System.out.println("完毕");
                // 等待子任务结果 或 去执行队列中的任务
                return calculateTask1.join() + calculateTask2.join();
            }
        }

    }

}
